package stack.easy;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * 1. 问题描述
 *
 * 2. 算法分析
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 删除字符串中的所有相邻重复项 {
    public static void main(String[] args){
        StringBuilder temp = new StringBuilder();
        temp.append('a');
        temp.append('b');
        temp.append('c');
        temp.append('d');
        temp.deleteCharAt(0);
        System.out.println(temp.toString());

    }

    /**
     * 栈结构实现  比较简单
     * @param S
     * @return
     */
    public String removeDuplicates1(String S) {
        Deque<Character> stack = new ArrayDeque<>();
        for(char ch : S.toCharArray()) {
            // 扫描当前每一个字符
            if(stack.isEmpty()) {
                stack.push(ch);
            }
            else {
                // 否则比较栈顶元素
                if(stack.peek() == ch) {
                    stack.pop();
                } else {
                    stack.push(ch);
                }
            }
        }
        StringBuilder ans = new StringBuilder();
        for(Character ch : stack) {
            ans.append(ch);
        }
        return ans.reverse().toString();
    }


    /**
     * 优化上述的代码实现，在进出栈的过程中记录当前的字符串，还是使用字符串流对象节省内存
     * 关键之处就是index的设置，记录了流对象中删除元素的信息，节省了最后的for循环，在遍历
     * 的过程中得到结果，但是效率任然不高，只超过了百分之60多
     * @param S
     * @return
     */
    public String removeDuplicates2(String S) {
        Deque<Character> stack = new ArrayDeque<>();
        StringBuilder ans = new StringBuilder(); // 记录结果
        int index = 0; // 记录ans中当前需要删除元素的索引
        for(int i = 0; i < S.length(); i++) {
            char ch = S.charAt(i); // 当前字符
            if(stack.isEmpty()) { // 如果栈空，直接进栈
                stack.push(ch);
                ans.append(ch);
                index++;
            } else {
                // 如果栈不空，我们需要比较当前栈顶元素是否与当前入栈元素相同
                if(stack.peek() == ch) {
                    // 如果当前入栈元素与栈顶元素相同，出栈
                    stack.pop();
                    ans.delete(index-1,index);
                    index--;
                } else {
                    // 如果不相同
                    ans.append(ch);
                    stack.push(ch);
                    index++;
                }
            }
        }
        return ans.toString();
    }

    /**
     * // 此时有如下情况
     *       // 1. ans为空 代码判断为index为0，直接让当前字符入栈
     *       // 2. ans不空 代码判断为index不为0，此时还是分两种情况：
     *             // 1. 如果当前入栈字符和栈顶元素字符相同，执行删除操作
     *             // 2. 如果不相同，直接入栈
     * @param S
     * @return
     */
    public String removeDuplicate3(String S) {
        StringBuilder ans = new StringBuilder(); // 记录结果
        int index = 0; // 处理ans中的元素删除
        for(Character ch : S.toCharArray()) {
            if(index == 0) {
                ans.append(ch);
                index++;
            } else {
                if(ch == ans.charAt(index-1)) {
                    ans.deleteCharAt(index-- - 1);
                } else {
                    ans.append(ch);
                    index++;
                }
            }
        }
        return ans.toString();
    }

    /**
     * leetcode官方给的解答，也是利用栈，但是代码比我的简洁太多了
     *
     * 主要是使用了StringBuilder类中的两个API
     * 1. deleteCharAt(int index) 删除
     * 2. CharAt(int index) 查看
     * @param S
     * @return
     */
    public String removeDuplicates4(String S) {
        StringBuilder sb = new StringBuilder(); // 记录结果
        int sbLength = 0; // 此变量的效果和我代码中的index作用类似
        for (char character : S.toCharArray()) { // 扫描S
            // 如果sbLength不为0，并且当前字符不等于
            if (sbLength != 0 && character == sb.charAt(sbLength - 1))
                sb.deleteCharAt(sbLength-- - 1);
            else {
                sb.append(character);
                sbLength++;
            }
        }
        return sb.toString();
    }

    /**
     * leetcode上大佬给的原地置换法  tql tql   时间和空间 与上述代码比最好的一个
     * 原地置换法不熟悉的一种算法，之前只见过一次，但是有必要对这个算法总结以下，非常强大的算法
     * 对一些问题有很好的优化(之前的一道题目就是通过原地置换法，将空间为O(n)的转换为O(1),效率不变)
     * 明天总结，别忘了!!!!!!!!! 淦
     * @param S
     * @return
     */
    public String removeDuplicates5(String S) {
        int idx = -1;
        char[] ss = S.toCharArray();
        for (int i = 0; i < S.length(); ++i) {
            if (idx == -1 || ss[idx] != ss[i]) {
                ss[++idx] = ss[i];
            } else if (ss[idx] == ss[i]) {
                idx--;
            }
        }
        return String.valueOf(Arrays.copyOfRange(ss, 0, idx + 1));
    }




}
